package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC529 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        public char[][] updateBoard(char[][] board, int[] click) {
            if (board[click[0]][click[1]] == 'M') {
                board[click[0]][click[1]] = 'X';
                return board;
            }

            boolean visited[][] = new boolean[board.length][board[0].length];
            Deque<int[]> queue = new LinkedList<>();
            queue.offerLast(click);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] cur = queue.pollFirst();
                    if (board[cur[0]][cur[1]] != 'E') continue;

                    int mineCount = getSurroundMineSituation(board, cur[0], cur[1]);
                    if (mineCount > 0) {
                        board[cur[0]][cur[1]] = (char) (mineCount + '0');
                        continue;
                    } else board[cur[0]][cur[1]] = 'B';

                    visited[cur[0]][cur[1]] = true;
                    int[] pos = {-1, 0, 1};
                    int surroundX, surroundY;
                    for (int vertical : pos) {
                        for (int horizontal : pos) {
                            if (vertical == 0 && horizontal == 0) continue;
                            surroundX = cur[0] + vertical;
                            surroundY = cur[1] + horizontal;
                            if (surroundX < 0 || surroundX >= board.length || surroundY < 0 || surroundY >= board[0].length)
                                continue;
                            if (visited[surroundX][surroundY]) continue;
                            queue.offer(new int[]{surroundX, surroundY});
                        }
                    }
                }
            }

            return board;
        }

        public int getSurroundMineSituation(char[][] board, int x, int y) {
            int mineCount = 0;
            int[] pos = {-1, 0, 1};
            int surroundX, surroundY;
            for (int vertical : pos) {
                for (int horizontal : pos) {
                    if (vertical == 0 && horizontal == 0) continue;
                    surroundX = x + vertical;
                    surroundY = y + horizontal;
                    if (surroundX < 0 || surroundX >= board.length || surroundY < 0 || surroundY >= board[0].length)
                        continue;
                    if (board[surroundX][surroundY] == 'M') ++mineCount;
                }
            }

            return mineCount;
        }

    }

    public void run() {
        Solution solution = new Solution();
        char[][] board = {{'E', 'E', 'E', 'E', 'E'}, {'E', 'E', 'M', 'E', 'E'}, {'E', 'E', 'E', 'E', 'E'}, {'E', 'E', 'E', 'E', 'E'}};
        System.out.println(solution.updateBoard(board, new int[]{3, 0}));
    }

    public static void main(String[] args) throws Exception {
        LC529 an = new LC529();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
